package com.xie.leetcode.tree;

//590. N 叉树的后序遍历
//        给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。
//
//        n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
//
//        示例 1：
//
//        输入：root = [1,null,3,2,4,null,5,6]
//        输出：[5,6,3,2,4,1]
//        示例 2：
//
//        输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
//        输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
//
//        提示：
//
//        节点总数在范围 [0, 10^4] 内
//        0 <= Node.val <= 10^4
//        n 叉树的高度小于或等于 1000

import com.xie.leetcode.base.Node;

import java.util.ArrayList;
import java.util.List;

/**
 * @author xiezhendong
 * @date 2022/03/12
 */
public class Postorder {

    public static void main(String[] args) {
        Node node1 = new Node(5);
        Node node2 = new Node(6);
        List<Node> node3List = new ArrayList<>();
        node3List.add(node1);
        node3List.add(node2);
        Node node3 = new Node(3, node3List);
        Node node4 = new Node(2);
        Node node5 = new Node(4);
        List<Node> node1List = new ArrayList<>();
        node1List.add(node4);
        node1List.add(node3);
        node1List.add(node5);

        Node node = new Node(1, node1List);

        Postorder postorder = new Postorder();
        System.out.println(postorder.postorder(node));

    }

    public List<Integer> postorder(Node root) {
        List<Integer> postorderList = new ArrayList<>();
        getNextList(postorderList, root);
        return postorderList;
    }

    private void getNextList(List<Integer> postorderList, Node node) {
        if (node == null) {
            return;
        }
        if (node.children != null && node.children.size() > 0) {
            for (Node childrenNode : node.children) {
                getNextList(postorderList, childrenNode);
            }
        }
        postorderList.add(node.val);
    }
}
